//===--- DynamicCasts.cpp - Utilities for dynamic casts -------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2018 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#include "polarphp/pil/lang/DynamicCasts.h"
#include "polarphp/ast/Module.h"
#include "polarphp/ast/InterfaceConformance.h"
#include "polarphp/ast/Types.h"
#include "polarphp/pil/lang/PILArgument.h"
#include "polarphp/pil/lang/PILBuilder.h"
#include "polarphp/pil/lang/TypeLowering.h"

using namespace polar;
using namespace polar::lowering;

static unsigned getAnyMetatypeDepth(CanType type) {
   unsigned depth = 0;
   while (auto metatype = dyn_cast<AnyMetatypeType>(type)) {
      type = metatype.getInstanceType();
      depth++;
   }
   return depth;
}

static bool
mayBridgeToObjectiveC(ModuleDecl *M, CanType T) {
   // FIXME: Disable when we don't support Objective-C interoperability?
   return true;
}

static bool
mustBridgeToPolarphpValueBox(ModuleDecl *M, CanType T) {
   // If the target type is either an unknown dynamic type, or statically
   // known to bridge, the cast may succeed.
   if (T->hasArchetype())
      return false;

   if (T->isAnyExistentialType())
      return false;
   /// @todo
//   // getBridgedToObjC() might return a null-type for some types
//   // whose bridging implementation is allowed to live elsewhere. Exclude this
//   // case here.
//   if (auto N = T->getAnyNominal())
//      if (M->getAstContext().isTypeBridgedInExternalModule(N))
//         return false;
//
//   return !M->getAstContext().getBridgedToObjC(M, T);
}

static bool canClassOrSuperclassesHaveUnknownSubclasses(ClassDecl *CD,
                                                        bool isWholeModuleOpts) {
   while (CD) {
      // Open classes can always have unknown subclasses.
      if (CD->getEffectiveAccess() == AccessLevel::Open)
         return true;

      // Internal and public classes may have unknown subclasses if we are not in
      // whole-module-optimization mode.
      if (CD->getEffectiveAccess() >= AccessLevel::Interface &&
          !isWholeModuleOpts)
         return true;

      if (!CD->hasSuperclass())
         break;

      CD = CD->getSuperclassDecl();
   }

   return false;
}

/// Try to classify a conversion from non-existential type
/// into an existential type by performing a static check
/// of protocol conformances if it is possible.
static DynamicCastFeasibility
classifyDynamicCastToInterface(ModuleDecl *M, CanType source, CanType target,
                              bool isWholeModuleOpts) {
   assert(target.isExistentialType() &&
          "target should be an existential type");

   if (source == target)
      return DynamicCastFeasibility::WillSucceed;

   auto *TargetInterface = cast_or_null<InterfaceDecl>(target.getAnyNominal());
   if (!TargetInterface)
      return DynamicCastFeasibility::MaySucceed;

   // If conformsToInterface returns a valid conformance, then all requirements
   // were proven by the type checker.
   if (M->conformsToInterface(source, TargetInterface))
      return DynamicCastFeasibility::WillSucceed;

   auto *SourceNominalTy = source.getAnyNominal();
   if (!SourceNominalTy)
      return DynamicCastFeasibility::MaySucceed;

   // Interface types may conform to their own protocols (or other protocols)
   // in the future.
   if (source->isAnyExistentialType()) {
      return DynamicCastFeasibility::MaySucceed;
   }

   // If it is a class and it can be proven that this class and its
   // superclasses cannot have unknown subclasses, then it is safe to proceed.
   if (auto *CD = source.getClassOrBoundGenericClass()) {
      if (canClassOrSuperclassesHaveUnknownSubclasses(CD, isWholeModuleOpts))
         return DynamicCastFeasibility::MaySucceed;
      // Derived types may conform to the protocol.
      if (!CD->isFinal()) {
         // TODO: If it is a private type or internal type and we
         // can prove that there are no derived types conforming to a
         // protocol, then we can still return WillFail.
         return DynamicCastFeasibility::MaySucceed;
      }
   }

   // The WillFail conditions below assume any possible conformance on the
   // nominal source type has been ruled out. The prior conformsToInterface query
   // identified any definite conformance. Now check if there is already a known
   // conditional conformance on the nominal type with requirements that were
   // not proven.
   //
   // TODO: The TypeChecker can easily prove that some requirements cannot be
   // met. Returning WillFail in those cases would be more optimal. To do that,
   // the conformsToInterface interface needs to be reformulated as a query, and
   // the implementation, including checkGenericArguments, needs to be taught to
   // recognize that types with archetypes may potentially succeed.
   if (auto conformance = M->lookupConformance(source, TargetInterface)) {
      assert(!conformance.getConditionalRequirements().empty());
      return DynamicCastFeasibility::MaySucceed;
   }

   // If the source type is file-private or target protocol is file-private,
   // then conformances cannot be changed at run-time, because only this
   // file could have implemented them, but no conformances were found.
   // Therefore it is safe to make a negative decision at compile-time.
   if (SourceNominalTy->getEffectiveAccess() <= AccessLevel::FilePrivate ||
       TargetInterface->getEffectiveAccess() <= AccessLevel::FilePrivate) {
      // This cast is always false. Replace it with a branch to the
      // failure block.
      return DynamicCastFeasibility::WillFail;
   }

   // AnyHashable is a special case: although it's a struct, there maybe another
   // type conforming to it and to the TargetInterface at the same time.
   if (SourceNominalTy == SourceNominalTy->getAstContext().getAnyHashableDecl())
      return DynamicCastFeasibility::MaySucceed;

   // If we are in a whole-module compilation and
   // if the source type is internal or target protocol is internal,
   // then conformances cannot be changed at run-time, because only this
   // module could have implemented them, but no conformances were found.
   // Therefore it is safe to make a negative decision at compile-time.
   if (isWholeModuleOpts &&
       (SourceNominalTy->getEffectiveAccess() <= AccessLevel::Interface ||
        TargetInterface->getEffectiveAccess() <= AccessLevel::Interface)) {
      return DynamicCastFeasibility::WillFail;
   }

   return DynamicCastFeasibility::MaySucceed;
}

static DynamicCastFeasibility
classifyDynamicCastFromInterface(ModuleDecl *M, CanType source, CanType target,
                                bool isWholeModuleOpts) {
   assert(source.isExistentialType() &&
          "source should be an existential type");

   if (source == target)
      return DynamicCastFeasibility::WillSucceed;

   // Casts from class existential into a non-class can never succeed.
   if (source->isClassExistentialType() &&
       !target.isAnyExistentialType() &&
       !target.getClassOrBoundGenericClass() &&
       !isa<ArchetypeType>(target) &&
       !mayBridgeToObjectiveC(M, target)) {
      assert((target.getEnumOrBoundGenericEnum() ||
              target.getStructOrBoundGenericStruct() ||
              isa<TupleType>(target) ||
              isa<PILFunctionType>(target) ||
              isa<FunctionType>(target) ||
              isa<MetatypeType>(target)) &&
             "Target should be an enum, struct, tuple, metatype or function type");
      return DynamicCastFeasibility::WillFail;
   }

   // TODO: maybe prove that certain conformances are impossible?

   return DynamicCastFeasibility::MaySucceed;
}

/// Returns the existential type associated with the Hashable
/// protocol, if it can be found.
static CanType getHashableExistentialType(ModuleDecl *M) {
   auto hashable =
      M->getAstContext().getInterface(KnownInterfaceKind::Hashable);
   if (!hashable) return CanType();
   return hashable->getDeclaredType()->getCanonicalType();
}

/// Check if a given type conforms to _BridgedToObjectiveC protocol.
bool polar::isObjectiveCBridgeable(ModuleDecl *M, CanType Ty) {
   // Retrieve the _BridgedToObjectiveC protocol.
   auto bridgedProto =
      M->getAstContext().getInterface(KnownInterfaceKind::ObjectiveCBridgeable);

   if (bridgedProto) {
      // Find the conformance of the value type to _BridgedToObjectiveC.
      // Check whether the type conforms to _BridgedToObjectiveC.
      return (bool)M->lookupConformance(Ty, bridgedProto);
   }
   return false;
}

/// Check if a given type conforms to _Error protocol.
bool polar::isError(ModuleDecl *M, CanType Ty) {
   // Retrieve the Error protocol.
   auto errorTypeProto =
      M->getAstContext().getInterface(KnownInterfaceKind::Error);

   if (errorTypeProto) {
      // Find the conformance of the value type to Error.
      // Check whether the type conforms to Error.
      return (bool)M->lookupConformance(Ty, errorTypeProto);
   }
   return false;
}

/// Given that a type is not statically known to be an optional type, check
/// whether it might dynamically be able to store an optional.
static bool canDynamicallyStoreOptional(CanType type) {
   assert(!type.getOptionalObjectType());
   return type->canDynamicallyBeOptionalType(/* includeExistential */ true);
}

/// Given two class types, check whether there's a hierarchy relationship
/// between them.
static DynamicCastFeasibility
classifyClassHierarchyCast(CanType source, CanType target) {
   // Upcast: if the target type statically matches a type in the
   // source type's hierarchy, this is a static upcast and the cast
   // will always succeed.
   if (target->isExactSuperclassOf(source))
      return DynamicCastFeasibility::WillSucceed;

   // Upcast: if the target type might dynamically match a type in the
   // source type's hierarchy, this might be an upcast, in which
   // case the cast might succeed.
   if (target->isBindableToSuperclassOf(source))
      return DynamicCastFeasibility::MaySucceed;

   // Downcast: if the source type might dynamically match a type in the
   // target type's hierarchy, this might be a downcast, in which case
   // the cast might succeed.  Note that this also covers the case where
   // the source type statically matches a type in the target type's
   // hierarchy; since it's a downcast, the cast still at best might succeed.
   if (source->isBindableToSuperclassOf(target))
      return DynamicCastFeasibility::MaySucceed;

   // Otherwise, the classes are unrelated and the cast will fail (at least
   // on these grounds).
   return DynamicCastFeasibility::WillFail;
}

// @todo
//CanType polar::getNSBridgedClassOfCFClass(ModuleDecl *M, CanType type) {
//   if (auto classDecl = type->getClassOrBoundGenericClass()) {
//      if (classDecl->getForeignClassKind() == ClassDecl::ForeignKind::CFType) {
//         if (auto bridgedAttr =
//            classDecl->getAttrs().getAttribute<ObjCBridgedAttr>()) {
//            auto bridgedClass = bridgedAttr->getObjCClass();
//            // TODO: this should handle generic classes properly.
//            if (!bridgedClass->isGenericContext()) {
//               return bridgedClass->getDeclaredInterfaceType()->getCanonicalType();
//            }
//         }
//      }
//   }
//   return CanType();
//}

static bool isCFBridgingConversion(ModuleDecl *M,
                                   CanType sourceFormalType,
                                   CanType targetFormalType) {
   if (auto bridgedTarget =
      getNSBridgedClassOfCFClass(M, targetFormalType)) {
      return bridgedTarget->isExactSuperclassOf(sourceFormalType);
   }
   if (auto bridgedSource =
      getNSBridgedClassOfCFClass(M, sourceFormalType)) {
      return targetFormalType->isExactSuperclassOf(bridgedSource);
   }

   return false;
}

/// Try to classify the dynamic-cast relationship between two types.
DynamicCastFeasibility
polar::classifyDynamicCast(ModuleDecl *M,
                           CanType source,
                           CanType target,
                           bool isSourceTypeExact,
                           bool isWholeModuleOpts) {
   if (source == target) return DynamicCastFeasibility::WillSucceed;

   // Return a conservative answer for opaque archetypes for now.
   if (source->hasOpaqueArchetype() || target->hasOpaqueArchetype())
      return DynamicCastFeasibility::MaySucceed;

   auto sourceObject = source.getOptionalObjectType();
   auto targetObject = target.getOptionalObjectType();

   // A common level of optionality doesn't affect the feasibility,
   // except that we can't fold things to failure because nil inhabits
   // both types.
   if (sourceObject && targetObject) {
      return atWorst(classifyDynamicCast(M, sourceObject, targetObject),
                     DynamicCastFeasibility::MaySucceed);

      // Casting to a more optional type follows the same rule unless we
      // know that the source cannot dynamically be an optional value,
      // in which case we'll always just cast and inject into an optional.
   } else if (targetObject) {
      auto result = classifyDynamicCast(M, source, targetObject,
         /* isSourceTypeExact */ false,
                                        isWholeModuleOpts);
      if (canDynamicallyStoreOptional(source))
         result = atWorst(result, DynamicCastFeasibility::MaySucceed);
      return result;

      // Casting to a less-optional type can always fail.
   } else if (sourceObject) {
      auto result = atBest(classifyDynamicCast(M, sourceObject, target,
                              /* isSourceTypeExact */ false,
                                               isWholeModuleOpts),
                           DynamicCastFeasibility::MaySucceed);
      if (target.isExistentialType()) {
         result = atWorst(result, classifyDynamicCastToInterface(
            M, source, target, isWholeModuleOpts));
      }
      return result;
   }
   assert(!sourceObject && !targetObject);

   // Assume that casts to or from existential types or involving
   // dependent types can always succeed.  This is over-conservative.
   if (source->hasArchetype() || source.isExistentialType() ||
       target->hasArchetype() || target.isExistentialType()) {

      // Check conversions from non-protocol types into protocol types.
      if (!source.isExistentialType() &&
          target.isExistentialType())
         return classifyDynamicCastToInterface(M, source, target,
                                              isWholeModuleOpts);

      // Check conversions from protocol types to non-protocol types.
      if (source.isExistentialType() &&
          !target.isExistentialType())
         return classifyDynamicCastFromInterface(M, source, target,
                                                isWholeModuleOpts);

      return DynamicCastFeasibility::MaySucceed;
   }

   // Casts from AnyHashable.
   if (auto sourceStruct = dyn_cast<StructType>(source)) {
      if (sourceStruct->getDecl() == M->getAstContext().getAnyHashableDecl()) {
         if (auto hashable = getHashableExistentialType(M)) {
            // Succeeds if Hashable can be cast to the target type.
            return classifyDynamicCastFromInterface(M, hashable, target,
                                                   isWholeModuleOpts);
         }
      }
   }

   // Casts to AnyHashable.
   if (auto targetStruct = dyn_cast<StructType>(target)) {
      if (targetStruct->getDecl() == M->getAstContext().getAnyHashableDecl()) {
         // Succeeds if the source type can be dynamically cast to Hashable.
         // Hashable is not actually a legal existential type right now, but
         // the check doesn't care about that.
         if (auto hashable = getHashableExistentialType(M)) {
            return classifyDynamicCastToInterface(M, source, hashable,
                                                 isWholeModuleOpts);
         }
      }
   }

   // Metatype casts.
   if (auto sourceMetatype = dyn_cast<AnyMetatypeType>(source)) {
      auto targetMetatype = dyn_cast<AnyMetatypeType>(target);
      if (!targetMetatype) return DynamicCastFeasibility::WillFail;

      source = sourceMetatype.getInstanceType();
      target = targetMetatype.getInstanceType();

      if (source == target &&
          targetMetatype.isAnyExistentialType() ==
          sourceMetatype.isAnyExistentialType())
         return DynamicCastFeasibility::WillSucceed;

      // If the source and target are the same existential type, but the source is
      // P.Interface and the dest is P.Type, then we need to consider whether the
      // protocol is self-conforming.
      // The only cases where a protocol self-conforms are objc protocols, but
      // we're going to expect P.Type to hold a class object. And this case
      // doesn't matter since for a self-conforming protocol type there can't be
      // any type-level methods.
      // Thus we consider this kind of cast to always fail. The only exception
      // from this rule is when the target is Any.Type, because *.Interface
      // can always be casted to Any.Type.
      if (source->isAnyExistentialType() && isa<MetatypeType>(sourceMetatype) &&
          isa<ExistentialMetatypeType>(targetMetatype)) {
         return target->isAny() ? DynamicCastFeasibility::WillSucceed
                                : DynamicCastFeasibility::WillFail;
      }

      if (targetMetatype.isAnyExistentialType() &&
          (isa<InterfaceType>(target) || isa<InterfaceCompositionType>(target))) {
         auto Feasibility =
            classifyDynamicCastToInterface(M, source, target, isWholeModuleOpts);
         // Cast from existential metatype to existential metatype may still
         // succeed, even if we cannot prove anything statically.
         if (Feasibility != DynamicCastFeasibility::WillFail ||
             !sourceMetatype.isAnyExistentialType())
            return Feasibility;
      }

      // If isSourceTypeExact is true, we know we are casting the result of a
      // MetatypeInst instruction.
      if (isSourceTypeExact) {
         // If source or target are existentials, then it can be cast
         // successfully only into itself.
         if ((target.isAnyExistentialType() || source.isAnyExistentialType()) &&
             target != source)
            return DynamicCastFeasibility::WillFail;
      }

      // Casts from class existential metatype into a concrete non-class metatype
      // can never succeed.
      if (source->isClassExistentialType() &&
          !target.isAnyExistentialType() &&
          !target.getClassOrBoundGenericClass())
         return DynamicCastFeasibility::WillFail;

      // TODO: prove that some conversions to existential metatype will
      // obviously succeed/fail.
      // TODO: prove that some conversions from class existential metatype
      // to a concrete non-class metatype will obviously fail.
      // TODO: class metatype to/from AnyObject
      // TODO: protocol concrete metatype to/from ObjCInterface
      if (isa<ExistentialMetatypeType>(sourceMetatype) ||
          isa<ExistentialMetatypeType>(targetMetatype))
         return (getAnyMetatypeDepth(source) == getAnyMetatypeDepth(target)
                 ? DynamicCastFeasibility::MaySucceed
                 : DynamicCastFeasibility::WillFail);

      // If both metatypes are class metatypes, check if classes can be
      // cast.
      if (source.getClassOrBoundGenericClass() &&
          target.getClassOrBoundGenericClass())
         return classifyClassHierarchyCast(source, target);

      // Different structs cannot be cast to each other.
      if (source.getStructOrBoundGenericStruct() &&
          target.getStructOrBoundGenericStruct() &&
          source != target)
         return DynamicCastFeasibility::WillFail;

      // Different enums cannot be cast to each other.
      if (source.getEnumOrBoundGenericEnum() &&
          target.getEnumOrBoundGenericEnum() &&
          source != target)
         return DynamicCastFeasibility::WillFail;

      // If we don't know any better, assume that the cast may succeed.
      return DynamicCastFeasibility::MaySucceed;
   }

   // Function casts.
   if (auto sourceFunction = dyn_cast<FunctionType>(source)) {
      if (auto targetFunction = dyn_cast<FunctionType>(target)) {
         // A function cast can succeed if the function types can be identical,
         // or if the target type is throwier than the original.

         // A non-throwing source function can be cast to a throwing target type,
         // but not vice versa.
         if (sourceFunction->throws() && !targetFunction->throws())
            return DynamicCastFeasibility::WillFail;

         // The cast can't change the representation at runtime.
         if (targetFunction->getRepresentation()
             != sourceFunction->getRepresentation())
            return DynamicCastFeasibility::WillFail;

         if (AnyFunctionType::equalParams(sourceFunction.getParams(),
                                          targetFunction.getParams()) &&
             sourceFunction.getResult() == targetFunction.getResult())
            return DynamicCastFeasibility::WillSucceed;

         // Be conservative about function type relationships we may add in
         // the future.
         return DynamicCastFeasibility::MaySucceed;
      }
   }

   // Tuple casts.
   if (auto sourceTuple = dyn_cast<TupleType>(source)) {
      if (auto targetTuple = dyn_cast<TupleType>(target)) {
         // # of elements must coincide.
         if (sourceTuple->getNumElements() != targetTuple->getNumElements())
            return DynamicCastFeasibility::WillFail;

         DynamicCastFeasibility result = DynamicCastFeasibility::WillSucceed;
         for (unsigned i : range(sourceTuple->getNumElements())) {
            const auto &sourceElt = sourceTuple->getElement(i);
            const auto &targetElt = targetTuple->getElement(i);

            // If both have names and the names mismatch, the cast will fail.
            if (sourceElt.hasName() && targetElt.hasName() &&
                sourceElt.getName() != targetElt.getName())
               return DynamicCastFeasibility::WillFail;

            // Combine the result of prior elements with this element type.
            result = std::max(result,
                              classifyDynamicCast(M,
                                                  sourceElt.getType()->getCanonicalType(),
                                                  targetElt.getType()->getCanonicalType(),
                                                  isSourceTypeExact,
                                                  isWholeModuleOpts));

            // If this element failed, we're done.
            if (result == DynamicCastFeasibility::WillFail)
               break;
         }

         return result;
      }
   }

   // Class casts.
   auto sourceClass = source.getClassOrBoundGenericClass();
   auto targetClass = target.getClassOrBoundGenericClass();
   if (sourceClass) {
      if (targetClass) {
         // Imported Objective-C generics don't check the generic parameters, which
         // are lost at runtime.
         /// @todo
//         if (sourceClass->usesObjCGenericsModel()) {
//
//            if (sourceClass == targetClass)
//               return DynamicCastFeasibility::WillSucceed;
//
//            if (targetClass->usesObjCGenericsModel()) {
//               // If both classes are ObjC generics, the cast may succeed if the
//               // classes are related, irrespective of their generic parameters.
//
//               if (sourceClass->isSuperclassOf(targetClass))
//                  return DynamicCastFeasibility::MaySucceed;
//
//               if (targetClass->isSuperclassOf(sourceClass))
//                  return DynamicCastFeasibility::WillSucceed;
//
//               return DynamicCastFeasibility::WillFail;
//            }
//         }

         // Try a hierarchy cast.  If that isn't failure, we can report it.
         auto hierarchyResult = classifyClassHierarchyCast(source, target);
         if (hierarchyResult != DynamicCastFeasibility::WillFail)
            return hierarchyResult;

         // As a backup, consider whether either type is a CF class type
         // with an NS bridged equivalent.
         CanType bridgedSource = getNSBridgedClassOfCFClass(M, source);
         CanType bridgedTarget = getNSBridgedClassOfCFClass(M, target);

         // If neither type qualifies, we're done.
         if (!bridgedSource && !bridgedTarget)
            return DynamicCastFeasibility::WillFail;

         // Otherwise, map over to the bridged types and try to answer the
         // question there.
         if (bridgedSource) source = bridgedSource;
         if (bridgedTarget) target = bridgedTarget;
         return classifyDynamicCast(M, source, target, false, isWholeModuleOpts);
      }

      // Casts from a class into a non-class can never succeed if the target must
      // be bridged to a SwiftValueBox. You would need an AnyObject source for
      // that.
      if (!target.isAnyExistentialType() &&
          !target.getClassOrBoundGenericClass() &&
          !isa<ArchetypeType>(target) &&
          mustBridgeToPolarphpValueBox(M, target)) {
         assert((target.getEnumOrBoundGenericEnum() ||
                 target.getStructOrBoundGenericStruct() ||
                 isa<TupleType>(target) ||
                 isa<PILFunctionType>(target) ||
                 isa<FunctionType>(target) ||
                 isa<MetatypeType>(target)) &&
                "Target should be an enum, struct, tuple, metatype or function type");
         return DynamicCastFeasibility::WillFail;
      }


      // In the Objective-C runtime, class metatypes are also class instances.
      // The cast may succeed if the target type can be inhabited by a class
      // metatype.
      // TODO: Narrow this to the sourceClass being exactly NSObject.
      if (M->getAstContext().LangOpts.EnableObjCInterop) {
         if (auto targetMeta = dyn_cast<MetatypeType>(target)) {
            if (isa<ArchetypeType>(targetMeta.getInstanceType())
                || targetMeta.getInstanceType()->mayHaveSuperclass())
               return DynamicCastFeasibility::MaySucceed;
         } else if (isa<ExistentialMetatypeType>(target)) {
            return DynamicCastFeasibility::MaySucceed;
         }
      }
   }

   // If the source is not existential, an archetype, or (under the ObjC runtime)
   // a class, and the destination is a metatype, there is no way the cast can
   // succeed.
   if (target->is<AnyMetatypeType>()) return DynamicCastFeasibility::WillFail;

   // FIXME: Be more careful with bridging conversions from
   // NSArray, NSDictionary and NSSet as they may fail?

   // We know that a cast from Int -> class foobar will fail.
   if (targetClass &&
       !source.isAnyExistentialType() &&
       !source.getClassOrBoundGenericClass() &&
       !isa<ArchetypeType>(source) &&
       mustBridgeToPolarphpValueBox(M, source)) {
      assert((source.getEnumOrBoundGenericEnum() ||
              source.getStructOrBoundGenericStruct() ||
              isa<TupleType>(source) ||
              isa<PILFunctionType>(source) ||
              isa<FunctionType>(source) ||
              isa<MetatypeType>(source)) &&
             "Source should be an enum, struct, tuple, metatype or function type");
      return DynamicCastFeasibility::WillFail;
   }

   // Check if there might be a bridging conversion.
   if (source->isBridgeableObjectType() && mayBridgeToObjectiveC(M, target)) {
      // Try to get the ObjC type which is bridged to target type.
      assert(!target.isAnyExistentialType());
      // ObjC-to-Swift casts may fail. And in most cases it is impossible to
      // statically predict the outcome. So, let's be conservative here.
      return DynamicCastFeasibility::MaySucceed;
   }

   if (target->isBridgeableObjectType() && mayBridgeToObjectiveC(M, source)) {
      // Try to get the ObjC type which is bridged to source type.
      assert(!source.isAnyExistentialType());
      // @todo
//      if (Type ObjCTy = M->getAstContext().getBridgedToObjC(M, source)) {
//         // If the bridged ObjC type is known, check if
//         // this type can be cast into target type.
//         return classifyDynamicCast(M,
//                                    ObjCTy->getCanonicalType(),
//                                    target,
//            /* isSourceTypeExact */ false, isWholeModuleOpts);
//      }
      return DynamicCastFeasibility::MaySucceed;
   }

   // Check if it is a cast between bridged error types.
   if (isError(M, source) && isError(M, target)) {
      // TODO: Cast to NSError succeeds always.
      return DynamicCastFeasibility::MaySucceed;
   }

   // Check for a viable collection cast.
   if (auto sourceStruct = dyn_cast<BoundGenericStructType>(source)) {
      if (auto targetStruct = dyn_cast<BoundGenericStructType>(target)) {
         // Both types have to be the same kind of collection.
         auto typeDecl = sourceStruct->getDecl();
         if (typeDecl == targetStruct->getDecl()) {
            auto sourceArgs = sourceStruct.getGenericArgs();
            auto targetArgs = targetStruct.getGenericArgs();

            // Note that we can never say that a collection cast is impossible:
            // a cast can always succeed on an empty collection.

            // Arrays and sets.
            if (typeDecl == M->getAstContext().getArrayDecl() ||
                typeDecl == M->getAstContext().getSetDecl()) {
               auto valueFeasibility =
                  classifyDynamicCast(M, sourceArgs[0], targetArgs[0]);
               return atWorst(valueFeasibility,
                              DynamicCastFeasibility::MaySucceed);

               // Dictionaries.
            } else if (typeDecl == M->getAstContext().getDictionaryDecl()) {
               auto keyFeasibility =
                  classifyDynamicCast(M, sourceArgs[0], targetArgs[0]);
               auto valueFeasibility =
                  classifyDynamicCast(M, sourceArgs[1], targetArgs[1]);
               return atWorst(atBest(keyFeasibility, valueFeasibility),
                              DynamicCastFeasibility::MaySucceed);
            }
         }
      }
   }

   return DynamicCastFeasibility::WillFail;
}

static unsigned getOptionalDepth(CanType type) {
   unsigned depth = 0;
   while (CanType objectType = type.getOptionalObjectType()) {
      depth++;
      type = objectType;
   }
   return depth;
}

namespace {
struct Source {
   PILValue Value;
   CanType FormalType;

   bool isAddress() const { return Value->getType().isAddress(); }

   PILType getPILType() const { return Value->getType(); }

   Source() = default;
   Source(PILValue value, CanType formalType)
      : Value(value), FormalType(formalType) {}
};

struct Target {
   PILValue Address;
   PILType LoweredType;
   CanType FormalType;

   bool isAddress() const { return (bool) Address; }

   Source asAddressSource() const {
      assert(isAddress());
      return { Address, FormalType };
   }
   Source asScalarSource(PILValue value) const {
      assert(!isAddress());
      assert(!value->getType().isAddress());
      return { value, FormalType };
   }
   PILType getPILType() const {
      if (isAddress())
         return Address->getType();
      else
         return LoweredType;
   }

   Target() = default;
   Target(PILValue address, CanType formalType)
      : Address(address), LoweredType(address->getType()),
        FormalType(formalType) {
      assert(LoweredType.isAddress());
   }
   Target(PILType loweredType, CanType formalType)
      : Address(), LoweredType(loweredType), FormalType(formalType) {
      assert(!loweredType.isAddress());
   }
};

class CastEmitter {
   PILBuilder &B;
   PILModule &M;
   AstContext &Ctx;
   PILLocation Loc;
   ModuleDecl *SwiftModule;
public:
   CastEmitter(PILBuilder &B, ModuleDecl *swiftModule, PILLocation loc)
      : B(B), M(B.getModule()), Ctx(M.getAstContext()), Loc(loc),
        SwiftModule(swiftModule) {}

   Source emitTopLevel(Source source, Target target) {
      unsigned sourceOptDepth = getOptionalDepth(source.FormalType);
      unsigned targetOptDepth = getOptionalDepth(target.FormalType);

      assert(sourceOptDepth <= targetOptDepth);
      return emitAndInjectIntoOptionals(source, target,
                                        targetOptDepth - sourceOptDepth);
   }

private:
   const TypeLowering &getTypeLowering(PILType type) {
      return B.getFunction().getTypeLowering(type);
   }

   PILValue getOwnedScalar(Source source, const TypeLowering &srcTL) {
      assert(!source.isAddress());
      return source.Value;
   }

   Source putOwnedScalar(PILValue scalar, Target target) {
      assert(scalar->getType() == target.LoweredType.getObjectType());
      if (!target.isAddress())
         return target.asScalarSource(scalar);

      auto &targetTL = getTypeLowering(target.LoweredType);
      targetTL.emitStoreOfCopy(B, Loc, scalar, target.Address,
                               IsInitialization);
      return target.asAddressSource();
   }

   Source emitSameType(Source source, Target target) {
      assert(source.FormalType == target.FormalType ||
             source.getPILType() == target.getPILType());

      auto &srcTL = getTypeLowering(source.Value->getType());

      // The destination always wants a +1 value, so make the source
      // +1 if it's a scalar.
      if (!source.isAddress()) {
         source.Value = getOwnedScalar(source, srcTL);
      }

      // If we've got a scalar and want a scalar, the source is
      // exactly right.
      if (!target.isAddress() && !source.isAddress())
         return source;

      // If the destination wants a non-address value, load
      if (!target.isAddress()) {
         PILValue value = srcTL.emitLoadOfCopy(B, Loc, source.Value, IsTake);
         return target.asScalarSource(value);
      }

      if (source.isAddress()) {
         srcTL.emitCopyInto(B, Loc, source.Value, target.Address,
                            IsTake, IsInitialization);
      } else {
         srcTL.emitStoreOfCopy(B, Loc, source.Value, target.Address,
                               IsInitialization);
      }
      return target.asAddressSource();
   }

   Source emit(Source source, Target target) {
      if (source.FormalType == target.FormalType ||
          source.getPILType() == target.getPILType())
         return emitSameType(source, target);

      // Handle subtype conversions involving optionals.
      if (auto sourceObjectType = source.FormalType.getOptionalObjectType()) {
         return emitOptionalToOptional(source, sourceObjectType, target);
      }
      assert(!target.FormalType.getOptionalObjectType());

      // The only other things we return WillSucceed for currently is
      // an upcast or CF/NS toll-free-bridging conversion.
      // FIXME: Upcasts between existential metatypes are not handled yet.
      // We should generate for it:
      // %openedSrcMetatype = open_existential srcMetatype
      // init_existential dstMetatype, %openedSrcMetatype
      auto &srcTL = getTypeLowering(source.Value->getType());
      PILValue value;
      if (source.isAddress()) {
         value = srcTL.emitLoadOfCopy(B, Loc, source.Value, IsTake);
      } else {
         value = getOwnedScalar(source, srcTL);
      }
      auto targetFormalTy = target.FormalType;
      auto targetLoweredTy =
         PILType::getPrimitiveObjectType(targetFormalTy);
      if (isCFBridgingConversion(SwiftModule,
                                 source.FormalType,
                                 targetFormalTy)) {
         value = B.createUncheckedRefCast(Loc, value, targetLoweredTy);
      } else {
         value = B.createUpcast(Loc, value, targetLoweredTy);
      }
      return putOwnedScalar(value, target);
   }

   Source emitAndInjectIntoOptionals(Source source, Target target,
                                     unsigned depth) {
      if (depth == 0)
         return emit(source, target);

      // Recurse.
      EmitSomeState state;
      Target objectTarget = prepareForEmitSome(target, state);
      Source objectSource =
         emitAndInjectIntoOptionals(source, objectTarget, depth - 1);
      return emitSome(objectSource, target, state);
   }

   Source emitOptionalToOptional(Source source,
                                 CanType sourceObjectType,
                                 Target target) {
      // Switch on the incoming value.
      PILBasicBlock *contBB = B.splitBlockForFallthrough();
      PILBasicBlock *noneBB = B.splitBlockForFallthrough();
      PILBasicBlock *someBB = B.splitBlockForFallthrough();

      // Emit the switch.
      std::pair<EnumElementDecl*, PILBasicBlock*> cases[] = {
         { Ctx.getOptionalSomeDecl(), someBB },
         { Ctx.getOptionalNoneDecl(), noneBB },
      };
      if (source.isAddress()) {
         B.createSwitchEnumAddr(Loc, source.Value, /*default*/ nullptr, cases);
      } else {
         B.createSwitchEnum(Loc, source.Value, /*default*/ nullptr, cases);
      }

      // Create the Some block, which recurses.
      B.setInsertionPoint(someBB);
      {
         auto sourceSomeDecl = Ctx.getOptionalSomeDecl();

         PILType loweredSourceObjectType =
            source.Value->getType().getEnumElementType(
               sourceSomeDecl, M, B.getTypeExpansionContext());

         // Form the target for the optional object.
         EmitSomeState state;
         Target objectTarget = prepareForEmitSome(target, state);

         // Form the source value.
         AllocStackInst *sourceTemp = nullptr;
         Source objectSource;
         if (source.isAddress()) {
            // TODO: add an instruction for non-destructively getting a
            // specific element's data.
            PILValue sourceAddr = source.Value;
            sourceAddr = B.createUncheckedTakeEnumDataAddr(Loc, sourceAddr,
                                                           sourceSomeDecl, loweredSourceObjectType);
            objectSource = Source(sourceAddr, sourceObjectType);
         } else {
            // switch enum always start as @owned.
            PILValue sourceObjectValue = someBB->createPhiArgument(
               loweredSourceObjectType, ValueOwnershipKind::Owned);
            objectSource = Source(sourceObjectValue, sourceObjectType);
         }

         Source resultObject = emit(objectSource, objectTarget);

         // Deallocate the source temporary if we needed one.
         if (sourceTemp) {
            B.createDeallocStack(Loc, sourceTemp);
         }

         Source result = emitSome(resultObject, target, state);
         assert(result.isAddress() == target.isAddress());
         if (target.isAddress()) {
            B.createBranch(Loc, contBB);
         } else {
            B.createBranch(Loc, contBB, { result.Value });
         }
      }

      // Create the None block.
      B.setInsertionPoint(noneBB);
      {
         Source result = emitNone(target);
         assert(result.isAddress() == target.isAddress());
         if (target.isAddress()) {
            B.createBranch(Loc, contBB);
         } else {
            B.createBranch(Loc, contBB, { result.Value });
         }
      }

      // Continuation block.
      B.setInsertionPoint(contBB);
      if (target.isAddress()) {
         return target.asAddressSource();
      } else {
         PILValue result = contBB->createPhiArgument(target.LoweredType,
                                                     ValueOwnershipKind::Owned);
         return target.asScalarSource(result);
      }
   }

   struct EmitSomeState {
      EnumElementDecl *SomeDecl;
   };

   Target prepareForEmitSome(Target target, EmitSomeState &state) {
      auto objectType = target.FormalType.getOptionalObjectType();
      assert(objectType && "emitting Some into non-optional type");

      auto someDecl = Ctx.getOptionalSomeDecl();
      state.SomeDecl = someDecl;

      PILType loweredObjectType = target.LoweredType.getEnumElementType(
         someDecl, M, B.getTypeExpansionContext());

      if (target.isAddress()) {
         PILValue objectAddr =
            B.createInitEnumDataAddr(Loc, target.Address, someDecl,
                                     loweredObjectType);
         return { objectAddr, objectType };
      } else {
         return { loweredObjectType, objectType };
      }
   }

   Source emitSome(Source source, Target target, EmitSomeState &state) {
      // If our target is an address, prepareForEmitSome should have set this
      // up so that we emitted directly into
      if (target.isAddress()) {
         B.createInjectEnumAddr(Loc, target.Address, state.SomeDecl);
         return target.asAddressSource();
      } else {
         auto &srcTL = getTypeLowering(source.Value->getType());
         auto sourceObject = getOwnedScalar(source, srcTL);
         auto source = B.createEnum(Loc, sourceObject, state.SomeDecl,
                                    target.LoweredType);
         return target.asScalarSource(source);
      }
   }

   Source emitNone(Target target) {
      auto noneDecl = Ctx.getOptionalNoneDecl();

      if (target.isAddress()) {
         B.createInjectEnumAddr(Loc, target.Address, noneDecl);
         return target.asAddressSource();
      } else {
         PILValue res = B.createEnum(Loc, nullptr, noneDecl, target.LoweredType);
         return target.asScalarSource(res);
      }
   }
};
} // end anonymous namespace

PILValue
polar::emitSuccessfulScalarUnconditionalCast(PILBuilder &B, PILLocation loc,
                                             PILDynamicCastInst dynamicCast) {
   return emitSuccessfulScalarUnconditionalCast(
      B, B.getModule().getPolarphpModule(), loc, dynamicCast.getSource(),
      dynamicCast.getTargetLoweredType(), dynamicCast.getSourceFormalType(),
      dynamicCast.getTargetFormalType(), dynamicCast.getInstruction());
}

/// Emit an unconditional scalar cast that's known to succeed.
PILValue
polar::emitSuccessfulScalarUnconditionalCast(PILBuilder &B, ModuleDecl *M,
                                             PILLocation loc, PILValue value,
                                             PILType targetLoweredType,
                                             CanType sourceFormalType,
                                             CanType targetFormalType,
                                             PILInstruction *existingCast) {
   assert(classifyDynamicCast(M, sourceFormalType, targetFormalType)
          == DynamicCastFeasibility::WillSucceed);

   // Casts to/from existential types cannot be further improved.
   if (sourceFormalType.isAnyExistentialType() ||
       targetFormalType.isAnyExistentialType()) {
      if (existingCast)
         // Indicate that the existing cast cannot be further improved.
         return PILValue();

      llvm_unreachable("Casts to/from existentials are not supported yet");
   }

   // Fast path changes that don't change the type.
   if (sourceFormalType == targetFormalType)
      return value;

   Source source(value, sourceFormalType);
   Target target(targetLoweredType, targetFormalType);
   Source result = CastEmitter(B, M, loc).emitTopLevel(source, target);
   assert(!result.isAddress());
   assert(result.Value->getType() == targetLoweredType);
   return result.Value;
}

bool polar::emitSuccessfulIndirectUnconditionalCast(
   PILBuilder &B, PILLocation loc, PILDynamicCastInst dynamicCast) {
   return emitSuccessfulIndirectUnconditionalCast(
      B, B.getModule().getPolarphpModule(), loc, dynamicCast.getSource(),
      dynamicCast.getSourceFormalType(), dynamicCast.getDest(),
      dynamicCast.getTargetFormalType(), dynamicCast.getInstruction());
}

bool polar::emitSuccessfulIndirectUnconditionalCast(
   PILBuilder &B, ModuleDecl *M, PILLocation loc, PILValue src,
   CanType sourceFormalType, PILValue dest, CanType targetFormalType,
   PILInstruction *existingCast) {
   assert(classifyDynamicCast(M, sourceFormalType, targetFormalType)
          == DynamicCastFeasibility::WillSucceed);

   assert(src->getType().isAddress());
   assert(dest->getType().isAddress());

   // Casts between the same types can be always handled here.
   // Casts from non-existentials into existentials and
   // vice-versa cannot be improved yet.
   // Casts between a value type and a class cannot be optimized.
   // Therefore generate a simple unconditional_checked_cast_aadr.

   if (src->getType() != dest->getType())
      if (src->getType().isAnyExistentialType() !=
          dest->getType().isAnyExistentialType() ||
          !(src->getType().getClassOrBoundGenericClass() &&
            dest->getType().getClassOrBoundGenericClass())) {

         // If there is an existing cast with the same arguments,
         // indicate we cannot improve it.
         if (existingCast) {
            auto *UCCAI = dyn_cast<UnconditionalCheckedCastAddrInst>(existingCast);
            if (UCCAI && UCCAI->getSrc() == src && UCCAI->getDest() == dest
                && UCCAI->getSourceFormalType() == sourceFormalType
                && UCCAI->getTargetFormalType() == targetFormalType) {
               // Indicate that the existing cast cannot be further improved.
               return false;
            }
         }

         B.createUnconditionalCheckedCastAddr(loc,
                                              src, sourceFormalType,
                                              dest, targetFormalType);
         return true;
      }

   Source source(src, sourceFormalType);
   Target target(dest, targetFormalType);
   Source result = CastEmitter(B, M, loc).emitTopLevel(source, target);
   assert(result.isAddress());
   assert(result.Value == dest);
   (void) result;
   return true;
}

/// Can the given cast be performed by the scalar checked-cast
/// instructions?
bool polar::canUseScalarCheckedCastInstructions(PILModule &M,
                                                CanType sourceFormalType,
                                                CanType targetFormalType) {
   // Look through one level of optionality on the source.
   auto objectType = sourceFormalType;
   if (auto type = objectType.getOptionalObjectType())
      objectType = type;

   // Casting to NSError needs to go through the indirect-cast case,
   // since it may conform to Error and require Error-to-NSError
   // bridging, unless we can statically see that the source type inherits
   // NSError.

   // A class-constrained archetype may be bound to NSError, unless it has a
   // non-NSError superclass constraint. Casts to archetypes thus must always be
   // indirect.
   if (auto archetype = targetFormalType->getAs<ArchetypeType>()) {
      // Only ever permit this if the source type is a reference type.
      if (!objectType.isAnyClassReferenceType())
         return false;

      auto super = archetype->getSuperclass();
      if (super.isNull())
         return false;

      // A base class constraint that isn't NSError rules out the archetype being
      // bound to NSError.
      if (M.getAstContext().LangOpts.EnableObjCInterop) {
         if (auto nserror = M.Types.getNSErrorType())
            return !super->isEqual(nserror);
      }

      // If NSError wasn't loaded, any base class constraint must not be NSError.
      return true;
   }

   if (M.getAstContext().LangOpts.EnableObjCInterop
       && targetFormalType == M.Types.getNSErrorType()) {
      // If we statically know the source is an NSError subclass, then the cast
      // can go through the scalar path (and it's trivially true so can be
      // killed).
      return targetFormalType->isExactSuperclassOf(objectType);
   }

   // Three supported cases:
   // - metatype to metatype
   // - metatype to object
   // - object to object
   if ((objectType.isAnyClassReferenceType() || isa<AnyMetatypeType>(objectType))
       && targetFormalType.isAnyClassReferenceType())
      return true;

   if (isa<AnyMetatypeType>(objectType) && isa<AnyMetatypeType>(targetFormalType))
      return true;

   // Otherwise, we need to use the general indirect-cast functions.
   return false;
}

/// Carry out the operations required for an indirect conditional cast
/// using a scalar cast operation.
void polar::emitIndirectConditionalCastWithScalar(
   PILBuilder &B, ModuleDecl *M, PILLocation loc,
   CastConsumptionKind consumption,
   PILValue srcAddr, CanType sourceFormalType,
   PILValue destAddr, CanType targetFormalType,
   PILBasicBlock *indirectSuccBB, PILBasicBlock *indirectFailBB,
   ProfileCounter TrueCount, ProfileCounter FalseCount) {
   assert(canUseScalarCheckedCastInstructions(B.getModule(),
                                              sourceFormalType, targetFormalType));

   // Create our successor and fail blocks.
   PILBasicBlock *scalarFailBB = B.splitBlockForFallthrough();
   PILBasicBlock *scalarSuccBB = B.splitBlockForFallthrough();

   // Always take; this works under an assumption that retaining the result is
   // equivalent to retaining the source. That means that these casts would not
   // be appropriate for bridging-like conversions.
   //
   // Our plan is:
   //
   // 1. If the original cast was a take_always cast, then we take from our
   // memory location in the caller, store the value into dest in the success
   // block, and perform a destroy of our default argument in the failure block.
   //
   // 2. If the original cast was copy_on_success, then with ownership we borrow,
   // copy in the success path and store back into the source slot after copying.
   //
   // 3. If the original cast was take_on_success, then on success we place the
   // casted value into dest and on failure, store the original value back into
   // src.
   PILType targetLoweredType = destAddr->getType().getObjectType();
   // Inline constructor
   auto srcValue = ([&]() -> PILValue {
      if (consumption == CastConsumptionKind::CopyOnSuccess)
         return B.emitLoadBorrowOperation(loc, srcAddr);
      return B.emitLoadValueOperation(loc, srcAddr, LoadOwnershipQualifier::Take);
   })();

   B.createCheckedCastBranch(loc, /*exact*/ false, srcValue, targetLoweredType,
                             targetFormalType, scalarSuccBB, scalarFailBB,
                             TrueCount, FalseCount);

   // Emit the success block.
   B.setInsertionPoint(scalarSuccBB); {
      PILValue succValue = scalarSuccBB->createPhiArgument(
         targetLoweredType, srcValue.getOwnershipKind());

      switch (consumption) {
         // On success, we take with both take_always and take_on_success.
         case CastConsumptionKind::TakeAlways:
         case CastConsumptionKind::TakeOnSuccess:
            break;
         case CastConsumptionKind::CopyOnSuccess: {
            PILValue originalSuccValue = succValue;
            succValue = B.emitCopyValueOperation(loc, succValue);
            B.emitEndBorrowOperation(loc, originalSuccValue);
            B.emitEndBorrowOperation(loc, srcValue);
            break;
         }
         case CastConsumptionKind::BorrowAlways:
            llvm_unreachable("should never see a borrow_always here");
      }

      // And then store the succValue into dest.
      B.emitStoreValueOperation(loc, succValue, destAddr,
                                StoreOwnershipQualifier::Init);
      B.createBranch(loc, indirectSuccBB);
   }

   // Emit the failure block.
   B.setInsertionPoint(scalarFailBB);
   {
      PILValue failValue = srcValue;

      // If we have ownership, we need to create something for the default
      // argument. Otherwise, we just use the input argument to the
      // checked_cast_br.
      if (B.hasOwnership()) {
         failValue = scalarFailBB->createPhiArgument(srcValue->getType(),
                                                     srcValue.getOwnershipKind());
      }

      switch (consumption) {
         case CastConsumptionKind::TakeAlways:
            // We need to destroy the fail value if we have take_always.
            B.emitDestroyValueOperation(loc, failValue);
            break;
         case CastConsumptionKind::TakeOnSuccess:
            // If we have take_on_success, since we failed, just store the value back
            // into the src location that we originally took from.
            B.emitStoreValueOperation(loc, failValue, srcAddr,
                                      StoreOwnershipQualifier::Init);
            break;
         case CastConsumptionKind::CopyOnSuccess:
            B.emitEndBorrowOperation(loc, failValue);
            B.emitEndBorrowOperation(loc, srcValue);
            break;
         case CastConsumptionKind::BorrowAlways:
            llvm_unreachable("borrow_on_success should never appear here");
      }

      B.createBranch(loc, indirectFailBB);
   }
}
